home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / cagdofst.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  12.1 KB  |  421 lines
  1. /******************************************************************************
  2. * CagdOfst.c - computes offset approximation to curves and surfaces.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, March. 93.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. #define MAX_OFFSET_IMPROVE_ITERS    20
  10. #define NORMAL_PERTURB            1e-3
  11. #define OFFSET_TRIM_EPS            1.25
  12.  
  13. /******************************************************************************
  14. * Given a curve and an offset amount Offset, returns an approximation to the  *
  15. * offset curve by offseting the control polygon in the normal direction.      *
  16. ******************************************************************************/
  17. CagdCrvStruct *CagdCrvOffset(CagdCrvStruct *Crv, CagdRType OffsetDist)
  18. {
  19.     CagdBType
  20.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  21.     int i, j,
  22.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType),
  23.     Order = Crv -> Order,
  24.     Length = Crv -> Length;
  25.     CagdBType
  26.     HasNewKV = FALSE;
  27.     CagdVecStruct *N;
  28.     CagdCrvStruct
  29.     *OffsetCrv = CagdCrvCopy(Crv);
  30.     CagdRType *Nodes, *NodePtr,
  31.     **Points = OffsetCrv -> Points,
  32.     *KV = NULL;
  33.  
  34.     switch (Crv -> GType) {
  35.     case CAGD_CBEZIER_TYPE:
  36.         HasNewKV = TRUE;
  37.         KV = BspKnotUniformOpen(Length, Order, NULL);
  38.         break;
  39.     case CAGD_CBSPLINE_TYPE:
  40.         KV = Crv -> KnotVector;
  41.         break;
  42.     case CAGD_CPOWER_TYPE:
  43.         FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  44.         return NULL;
  45.     default:
  46.         FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  47.         return NULL;
  48.     }
  49.  
  50.     Nodes = BspKnotNodes(KV, Length + Order, Order);
  51.     NodePtr = Nodes;
  52.  
  53.     if (IsNotRational)
  54.     for (j = 0; j < Length; j++, NodePtr++) {
  55.         if ((N = CagdCrvNormal(Crv, *NodePtr)) == NULL &&
  56.         (N = CagdCrvNormal(Crv, NodePtr == Nodes ?
  57.                         *NodePtr + NORMAL_PERTURB :
  58.                         *NodePtr - NORMAL_PERTURB)) == NULL) {
  59.         FATAL_ERROR(CAGD_ERR_CANNOT_COMP_NORMAL);
  60.         return NULL;
  61.         }
  62.         for (i = 1; i <= MaxCoord; i++)
  63.         Points[i][j] += N -> Vec[i - 1] * OffsetDist;
  64.     }
  65.     else
  66.     for (j = 0; j < Length; j++, NodePtr++) {
  67.         if ((N = CagdCrvNormal(Crv, *NodePtr)) == NULL &&
  68.         (N = CagdCrvNormal(Crv, NodePtr == Nodes ?
  69.                         *NodePtr + NORMAL_PERTURB :
  70.                         *NodePtr - NORMAL_PERTURB)) == NULL) {
  71.         FATAL_ERROR(CAGD_ERR_CANNOT_COMP_NORMAL);
  72.         return NULL;
  73.         }
  74.         for (i = 1; i <= MaxCoord; i++)
  75.         Points[i][j] = Points[i][j] +
  76.                    N -> Vec[i - 1] * OffsetDist * Points[W][j];
  77.     }
  78.  
  79.     if (HasNewKV)
  80.     IritFree((VoidPtr) KV);
  81.     IritFree((VoidPtr) Nodes);
  82.  
  83.     return OffsetCrv;
  84. }
  85.  
  86. /******************************************************************************
  87. * Given a surface and an offset amount Offset, returns an approximation to    *
  88. * the offset surface by offseting the control mesh in the normal direction.   *
  89. ******************************************************************************/
  90. CagdSrfStruct *CagdSrfOffset(CagdSrfStruct *Srf, CagdRType OffsetDist)
  91. {
  92.     CagdBType
  93.     IsNotRational = !CAGD_IS_RATIONAL_SRF(Srf);
  94.     int    i, Row, Col,
  95.     MaxCoord = CAGD_NUM_OF_PT_COORD(Srf -> PType),
  96.     UOrder = Srf -> UOrder,
  97.     VOrder = Srf -> VOrder,
  98.     ULength = Srf -> ULength,
  99.     VLength = Srf -> VLength;
  100.     CagdBType
  101.     HasNewKV = FALSE;
  102.     CagdVecStruct *N;
  103.     CagdSrfStruct
  104.     *OffsetSrf = CagdSrfCopy(Srf);
  105.     CagdRType *UNodes, *VNodes, *UNodePtr, *VNodePtr,
  106.     **Points = OffsetSrf -> Points,
  107.     *UKV = NULL,
  108.     *VKV = NULL;
  109.  
  110.     switch (Srf -> GType) {
  111.     case CAGD_SBEZIER_TYPE:
  112.         HasNewKV = TRUE;
  113.         UKV = BspKnotUniformOpen(ULength, UOrder, NULL);
  114.         VKV = BspKnotUniformOpen(VLength, VOrder, NULL);
  115.         break;
  116.     case CAGD_SBSPLINE_TYPE:
  117.         UKV = Srf -> UKnotVector;
  118.         VKV = Srf -> VKnotVector;
  119.         break;
  120.     case CAGD_SPOWER_TYPE:
  121.         FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  122.         return NULL;
  123.     default:
  124.         FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  125.         return NULL;
  126.     }
  127.  
  128.     UNodes = BspKnotNodes(UKV, ULength + UOrder, UOrder);
  129.     VNodes = BspKnotNodes(VKV, VLength + VOrder, VOrder);
  130.  
  131.     if (IsNotRational)
  132.     for (Row = 0, VNodePtr = VNodes; Row < VLength; Row++, VNodePtr++)
  133.         for (Col = 0, UNodePtr = UNodes; Col < ULength; Col++, UNodePtr++) {
  134.             N = CagdSrfNormal(Srf, *UNodePtr, *VNodePtr);
  135.             for (i = 1; i <= MaxCoord; i++)
  136.             Points[i][CAGD_MESH_UV(OffsetSrf, Col, Row)] +=
  137.             N -> Vec[i - 1] * OffsetDist;
  138.         }
  139.     else
  140.     for (Row = 0, VNodePtr = VNodes; Row < VLength; Row++, VNodePtr++)
  141.         for (Col = 0, UNodePtr = UNodes; Col < ULength; Col++, UNodePtr++) {
  142.             N = CagdSrfNormal(Srf, *UNodePtr, *VNodePtr);
  143.             for (i = 1; i <= MaxCoord; i++)
  144.                 Points[i][CAGD_MESH_UV(OffsetSrf, Col, Row)] +=
  145.             N -> Vec[i - 1] * OffsetDist *
  146.                 Points[W][CAGD_MESH_UV(OffsetSrf, Col, Row)];
  147.         }
  148.  
  149.     if (HasNewKV) {
  150.     IritFree((VoidPtr) UKV);
  151.     IritFree((VoidPtr) VKV);
  152.     }
  153.  
  154.     IritFree((VoidPtr) UNodes);
  155.     IritFree((VoidPtr) VNodes);
  156.  
  157.     return OffsetSrf;
  158. }
  159.  
  160. /******************************************************************************
  161. * Given a curve and an offset amount OffsetDist, returns an approx. to the    *
  162. * offset curve by offseting the control polygon in the normal direction.      *
  163. *   This function computes an approximation to the offset using              *
  164. * OffsetAprxFunc, measure the error and use it to refine and decrease the     *
  165. * error. Bezier curves are promoted to Bsplines. See paper below for more.    *
  166. *                                          *
  167. * + Gershon Elber and Elaine Cohen. Error Bounded Variable Distance Offset    *
  168. *   Operator for Free Form Curves and Surfaces. International Journal of      *
  169. *   Computational Geometry & Applications, Vol. 1, Num. 1, March 1991,        *
  170. *   pp 67-78.                                      *
  171. ******************************************************************************/
  172. CagdCrvStruct *CagdCrvAdapOffset(CagdCrvStruct *OrigCrv,
  173.                  CagdRType OffsetDist,
  174.                  CagdRType OffsetError,
  175.                  CagdCrvFuncType OffsetAprxFunc)
  176. {
  177.     int i;
  178.     CagdBType
  179.     IsRational = CAGD_IS_RATIONAL_CRV(OrigCrv);
  180.     CagdRType Min, Max, TMin, TMax,
  181.     OffsetDistSqr = SQR(OffsetDist);
  182.     CagdCrvStruct *OffsetCrv, *Crv;
  183.  
  184.     switch (OrigCrv -> GType) {
  185.     case CAGD_CBEZIER_TYPE:
  186.         Crv = CnvrtBezier2BsplineCrv(OrigCrv);
  187.         break;
  188.     case CAGD_CBSPLINE_TYPE:
  189.         Crv = CagdCrvCopy(OrigCrv);
  190.         break;
  191.     case CAGD_CPOWER_TYPE:
  192.     default:
  193.         FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  194.         Crv = NULL;
  195.         break;
  196.     }
  197.  
  198.     if (OffsetAprxFunc == NULL)
  199.     OffsetAprxFunc = CagdCrvOffset;
  200.  
  201.     CagdCrvDomain(Crv, &TMin, &TMax);
  202.  
  203.     for (i = 0; i < MAX_OFFSET_IMPROVE_ITERS; i++) {
  204.     CagdCrvStruct *DiffCrv, *DistSqrCrv;
  205.  
  206.     OffsetCrv = OffsetAprxFunc(Crv, OffsetDist);
  207.     DiffCrv = CagdCrvSub(OffsetCrv, Crv);
  208.     DistSqrCrv = CagdCrvDotProd(DiffCrv, DiffCrv);
  209.     CagdCrvFree(DiffCrv);
  210.  
  211.     CagdCrvMinMax(DistSqrCrv, 1, &Min, &Max);
  212.  
  213.     if (OffsetDistSqr - Min < OffsetError &&
  214.         Max - OffsetDistSqr < OffsetError) {
  215.         /* Error is within bounds - returns this offset approximation. */
  216.         CagdCrvFree(DistSqrCrv);
  217.         break;
  218.     }
  219.     else {
  220.         /* Refine in regions where the error is too large. */
  221.         int j, k,
  222.             Length = DistSqrCrv -> Length,
  223.             Order = DistSqrCrv -> Order,
  224.             KVLen = Length + Order;
  225.         CagdRType
  226.         *KV = DistSqrCrv -> KnotVector,
  227.         *Nodes = BspKnotNodes(KV, KVLen, Order),
  228.         *RefKV = (CagdRType *) IritMalloc(sizeof(CagdRType) * 2 * Length);
  229.  
  230.         for (j = k = 0; j < Length; j++) {
  231.         CagdRType
  232.             *Pt = CagdCrvEval(DistSqrCrv, Nodes[j]),
  233.             V = OffsetDistSqr - (IsRational ? Pt[1] / Pt[0] : Pt[1]);
  234.  
  235.         if (ABS(V) > OffsetError) {
  236.             int Index = BspKnotLastIndexLE(KV, KVLen, Nodes[j]);
  237.  
  238.             if (APX_EQ(KV[Index], Nodes[j])) {
  239.             if (j > 0)
  240.                 RefKV[k++] = (Nodes[j] + Nodes[j - 1]) / 2.0;
  241.             if (j < Length - 1)
  242.                 RefKV[k++] = (Nodes[j] + Nodes[j + 1]) / 2.0;
  243.             }
  244.             else
  245.             RefKV[k++] = Nodes[j];
  246.         }
  247.         }
  248.         CagdCrvFree(DistSqrCrv);
  249.         IritFree((VoidPtr) Nodes);
  250.  
  251.         if (k == 0) {
  252.         /* No refinement was found needed - return current curve. */
  253.         IritFree((VoidPtr) RefKV);
  254.         break;
  255.         }
  256.         else {
  257.         CagdCrvStruct
  258.             *CTmp = CagdCrvRefineAtParams(Crv, FALSE, RefKV, k);
  259.  
  260.         IritFree((VoidPtr) RefKV);
  261.         CagdCrvFree(Crv);
  262.         Crv = CTmp;
  263.         }
  264.     }
  265.     }
  266.  
  267.     CagdCrvFree(Crv);
  268.     return OffsetCrv;
  269. }
  270.  
  271. /******************************************************************************
  272. * Same as CagdCrvAdapOffset, but trims the self intersection loops.          *
  273. * See paper below for more.                              *
  274. *                                          *
  275. * + Gershon Elber and Elaine Cohen. Error Bounded Variable Distance Offset    *
  276. *   Operator for Free Form Curves and Surfaces. International Journal of      *
  277. *   Computational Geometry & Applications, Vol. 1, Num. 1, March 1991,        *
  278. *   pp 67-78.                                      *
  279. ******************************************************************************/
  280. CagdCrvStruct *CagdCrvAdapOffsetTrim(CagdCrvStruct *OrigCrv,
  281.                      CagdRType OffsetDist,
  282.                      CagdRType OffsetError,
  283.                      CagdCrvFuncType OffsetAprxFunc)
  284. {
  285.     CagdBType
  286.         IsRational = CAGD_IS_RATIONAL_CRV(OrigCrv);
  287.     CagdCrvStruct *CrvtrSqr, *CrvtrSign, *Crv, *Crvs, *LastCrv,
  288.     *CrvOffsetList = NULL;
  289.     CagdPtStruct *Pts, *PtsHead, *LastPts;
  290.     CagdRType
  291.         OffsetDistSqr1 = 1.0 / SQR(OffsetDist);
  292.  
  293.     switch (OrigCrv -> GType) {
  294.     case CAGD_CBEZIER_TYPE:
  295.         Crv = CnvrtBezier2BsplineCrv(OrigCrv);
  296.         break;
  297.     case CAGD_CBSPLINE_TYPE:
  298.         Crv = CagdCrvCopy(OrigCrv);
  299.         break;
  300.     default:
  301.         FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  302.         break;
  303.     }
  304.  
  305.     if (OffsetDist == 0.0)
  306.     return Crv;
  307.  
  308.     CrvtrSqr = CagdCrvCurvatureSqr(Crv);
  309.     CrvtrSign = CagdCrvCurvatureSign(Crv);
  310.  
  311.     PtsHead = CagdCrvConstSet(CrvtrSqr, 1, SQR(OffsetError),
  312.                   OffsetDistSqr1 / SQR(OFFSET_TRIM_EPS));
  313.  
  314.     for (Pts = PtsHead, LastPts = NULL; Pts != NULL;) {
  315.     CagdRType *CrvtrSignPt, CrvtrSignVal;
  316.  
  317.     CrvtrSignPt = CagdCrvEval(CrvtrSign, Pts -> Pt[0]);
  318.     CrvtrSignVal = IsRational ? CrvtrSignPt[1] / CrvtrSignPt[0]
  319.                   : CrvtrSignPt[1];
  320.  
  321.     if (CrvtrSignVal * OffsetDist > 0.0) {
  322.         /* Remove point from list. */
  323.         if (LastPts != NULL) {
  324.         LastPts -> Pnext = Pts -> Pnext;
  325.         IritFree((VoidPtr) Pts);
  326.         Pts = LastPts -> Pnext;
  327.         }
  328.         else {
  329.         PtsHead = PtsHead -> Pnext;
  330.         IritFree((VoidPtr) Pts);
  331.         Pts = PtsHead;
  332.         }
  333.     }
  334.     else {
  335.         LastPts = Pts;
  336.         Pts = Pts -> Pnext;
  337.     }
  338.     }
  339.  
  340.     for (Pts = PtsHead;
  341.      Pts != NULL || Crv != NULL;
  342.      Pts = (Pts != NULL ? Pts -> Pnext : NULL)) {
  343.     CagdCrvStruct
  344.         *Crv1 = Pts ? CagdCrvSubdivAtParam(Crv, Pts -> Pt[0])
  345.             : CagdCrvCopy(Crv),
  346.         *Crv2 = Pts ? Crv1 -> Pnext : NULL;
  347.     CagdRType Min, Max, *CrvtrSqrPt, CrvtrSqrVal,
  348.                         *CrvtrSignPt, CrvtrSignVal;
  349.  
  350.     CagdCrvDomain(Crv1, &Min, &Max);
  351.  
  352.     CrvtrSqrPt = CagdCrvEval(CrvtrSqr, (Min + Max) / 2);
  353.     CrvtrSqrVal = CrvtrSqrPt[1] / CrvtrSqrPt[0];
  354.     CrvtrSignPt = CagdCrvEval(CrvtrSign, (Min + Max) / 2);
  355.     CrvtrSignVal = IsRational ? CrvtrSignPt[1] / CrvtrSignPt[0]
  356.                   : CrvtrSignPt[1];
  357.  
  358.     if (CrvtrSqrVal < OffsetDistSqr1 / SQR(OFFSET_TRIM_EPS) ||
  359.         CrvtrSignVal * OffsetDist > 0.0) {
  360.         CagdCrvStruct
  361.         *Crv1Off = CagdCrvAdapOffset(Crv1, OffsetDist, OffsetError,
  362.                          OffsetAprxFunc);
  363.  
  364.         CAGD_LIST_PUSH(Crv1Off, CrvOffsetList);
  365.     }
  366.  
  367.     CagdCrvFree(Crv1);
  368.     CagdCrvFree(Crv);
  369.     Crv = Crv2;
  370.     }
  371.  
  372.     Crvs = CagdListReverse(CrvOffsetList);
  373.     CrvOffsetList = NULL;
  374.     LastCrv = Crvs;
  375.     Crvs = Crvs -> Pnext;
  376.     for (Crv = Crvs; Crv != NULL; Crv = Crv -> Pnext) {
  377.     CagdCrvStruct *CTmp, *CTmp2;
  378.     CagdSrfStruct
  379.         *DistSrf = CagdSrfDistCrvCrv(LastCrv, Crv);
  380.     CagdPtStruct
  381.         *IPts = CagdSrfDistFindPoints(DistSrf, OffsetError, FALSE);
  382.  
  383.     CagdSrfFree(DistSrf);
  384.  
  385.     if (IPts != NULL) {
  386.         if (IPts -> Pnext) {
  387.         FATAL_ERROR(CAGD_ERR_TOO_COMPLEX);
  388.         return NULL;
  389.         }
  390.         else {
  391.         CagdRType TMin, TMax;
  392.  
  393.         CagdCrvDomain(LastCrv, &TMin, &TMax);
  394.         CTmp = CagdCrvRegionFromCrv(LastCrv, TMin, IPts -> Pt[0]);
  395.         CagdCrvFree(LastCrv);
  396.         LastCrv = CTmp;
  397.  
  398.         CagdCrvDomain(Crv, &TMin, &TMax);
  399.         CTmp = CagdCrvRegionFromCrv(Crv, IPts -> Pt[1], TMax);
  400.  
  401.         CTmp2 = CagdMergeCrvCrv(LastCrv, CTmp);
  402.         CagdCrvFree(CTmp);
  403.         CagdCrvFree(LastCrv);
  404.         LastCrv = CTmp2;
  405.         }
  406.     }
  407.     else {
  408.         /* Simply chain the pieces together. */
  409.         CTmp = CagdMergeCrvCrv(LastCrv, Crv);
  410.         CagdCrvFree(LastCrv);
  411.         LastCrv = CTmp;
  412.     }
  413.     }
  414.  
  415.     CagdPtFreeList(PtsHead);
  416.     CagdCrvFree(CrvtrSqr);
  417.     CagdCrvFree(CrvtrSign);
  418.  
  419.     return LastCrv;
  420. }
  421.